package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         108,
		Discription: "将升序数组转化为二叉搜索树",
		Level:       1,
		Labels: map[string]int{
			"递归":    1,
			"二叉树":   1,
			"二叉搜索树": 1,
		},
	})
}

// SortedArrayToBST 构造的二叉搜索树不唯一
//
//	@param nums
//	@return *ds.TreeNode
func SortedArrayToBST(nums []int) *ds.TreeNode {
	var build func(int, int) *ds.TreeNode
	build = func(start int, end int) *ds.TreeNode {
		if start > end {
			return nil
		}

		//每次取数组中中间偏左的那个元素作为根节点
		mid := (start + end) / 2
		node := &ds.TreeNode{
			Val: nums[mid],
		}
		node.Left = build(start, mid-1)
		node.Right = build(mid+1, end)
		return node
	}

	return build(0, len(nums)-1)
}
